package java0407;

import java.lang.reflect.Array;
import java.util.ArrayList;
import java.util.Collection;
import java.util.Collections;
import java.util.List;

public class Solution {

    // 最大连续1的个数
    // 给定一个二进制数组， 计算其中最大连续 1 的个数。
    public int findMaxConsecutiveOnes(int[] nums) {
        if (nums == null) {
            return 0;
        }
//        List<Integer> list = new ArrayList<>();
//        boolean flag = true;// 标志位标志前面是否为1
//        int ret = 0;
//        for (int i = 0; i < nums.length; i++) {
//            if (nums[i] == 1) {
//                if (flag == true) {
//                    ret++;
//                }else {
//                    flag = true;
//                    ret = 1;
//                }
//            }else {
//                flag = false;
//                list.add(ret);
//            }
//        }
//        if (flag == true) {
//            list.add(ret);
//        }
//        Collections.sort(list);
//        return list.get(list.size() - 1);
        int count = 0;
        int maxCount = 0;
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] == 1) {
                count++;
            }else {
                maxCount = maxCount > count ? maxCount : count;
                count = 0;
            }
        }
        maxCount = maxCount > count ? maxCount : count;
        return maxCount;
    }

    // 长度最小的子数组
    // 给定一个含有 n 个正整数的数组和一个正整数 target 。
    //
    //找出该数组中满足其和 ≥ target 的长度最小的 连续子数组 [numsl, numsl+1, ..., numsr-1, numsr] ，并返回其长度。如果不存在符合条件的子数组，返回 0 。
    // 输入：target = 7, nums = [2,3,1,2,4,3]
    //输出：2
    //解释：子数组 [4,3] 是该条件下的长度最小的子数组。
    public int minSubArrayLen(int target, int[] nums) {
        int minLength = 19999;
        int count = 0;
        for (int i = 0; i < nums.length; i++) {
            count = 0;
            for (int j = i; j < nums.length; j++) {
                count += nums[j];
                if (count >= target) {
                    minLength = minLength < (j - i + 1) ? minLength : (j - i + 1);
                    break;
                }
            }
        }
        if (minLength == 19999) {
            return 0;
        }
        return minLength;
    }

    // 杨辉三角
    // 给定一个非负整数 numRows，生成杨辉三角的前 numRows 行。
//    输入: 5
//    输出:
//            [
//            [1],
//            [1,1],
//            [1,2,1],
//            [1,3,3,1],
//            [1,4,6,4,1]
//            ]
    public List<List<Integer>> generate(int numRows) {
        List<List<Integer>> list = new ArrayList<>();
        if (numRows == 0) {
            return list;
        }
        for (int i = 0; i < numRows; i++) {
            List<Integer> row = new ArrayList<>();
            for (int j = 0; j <= i; j++) {
                if (j == 0) {
                    row.add(1);
                }else if (j < i) {
                    int a = list.get(i - 1).get(j - 1);
                    int b = list.get(i - 1).get(j);
                    row.add(a + b);
                }else {
                    row.add(1);
                }
            }
            list.add(row);
        }
        return list;
    }

    // 杨辉三角 II
    // 给定一个非负索引 k，其中 k ≤ 33，返回杨辉三角的第 k 行。
    //在杨辉三角中，每个数是它左上方和右上方的数的和。
    //示例
    //输入: 3
    //输出: [1,3,3,1]
    public List<Integer> getRow(int rowIndex) {
        int[][] yang = new int[rowIndex + 1][rowIndex + 1];
        for (int i = 0; i < rowIndex + 1; i++) {
            for (int j = 0; j <= i; j++) {
                if (j == 0) {
                    yang[i][j] = 1;
                }else if (j < i) {
                    yang[i][j] = yang[i - 1][j - 1] + yang[i - 1][j];
                }else {
                    yang[i][j] = 1;
                }
            }
        }
        List<Integer> ret = new ArrayList<>();
        for (int x : yang[rowIndex]) {
            ret.add(x);
        }
        return ret;
    }

    // 反转字符串中的单词 III
    // 给定一个字符串，你需要反转字符串中每个单词的字符顺序，同时仍保留空格和单词的初始顺序。
    //示例：
    //输入："Let's take LeetCode contest"
    //输出："s'teL ekat edoCteeL tsetnoc"
    public String reverseWords(String s) {
        char[] chars = s.toCharArray();
        int show = -1;
        int fast = 0;
        while (fast < chars.length) {
            if (s.charAt(fast) == ' ') {
                reversal(chars, show, fast);
                show = fast;
            }
            fast++;
        }
        if (chars[chars.length - 1] != ' ') {
            reversal(chars, show, chars.length);
        }
        return new String(chars);
    }

    private void reversal(char[] chars, int show, int fast) {
        int left = show + 1;
        int right = fast - 1;
        while (left < right) {
            char tmp = chars[left];
            chars[left] = chars[right];
            chars[right] = tmp;
            left++;
            right--;
        }
    }

}
